package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/11/17 18:58
 */
@SuppressWarnings("DuplicatedCode")
public class LC28实现strStr {

    public static int strStr(String haystack, String needle) {
        if (needle.length() > haystack.length()) return -1;
        if (haystack.length() == 0 || needle.length() == 0) return 0;
        return kmpSearch(haystack, needle);
    }

    public static void main(String[] args) {
        System.out.println(strStr("hello", "ll"));
    }

    private static int kmpSearch(String s, String p) {
        //找到next数组
        int[] next = new int[p.length()];
        for (int i = 1, j = 0; i < p.length(); i++) {
            while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
            if (p.charAt(i) == p.charAt(j)) j++;
            next[i] = j;
        }
        //利用next数组对字符串进行匹配
        for (int i = 0, j = 0; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != p.charAt(j)) j = next[j - 1];
            if (s.charAt(i) == p.charAt(j)) j++;
            if (j == p.length()) return i - j + 1;
        }
        return -1;
    }
}
